package com.my.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Created by Scarlett on 2018/10/8.
 * <p>
 * 快速排序
 * 选取一个基准元素，将数组中小于基准元素的排在数组左边，大于基准元素的排在数组右边
 * 针对左右两部分数组元素，递归这一过程，最终得到有序数组
 * <p>
 * 复杂度 N*LOG2(N)
 */
public class QuickSorter<T extends Comparable<T>> implements Sortable<T> {
    private static final Logger LOGGER = LoggerFactory.getLogger(QuickSorter.class);

    @Override
    public T[] sort(T[] elements) {
        if (elements == null || elements.length < 2) {
            return elements;
        }


        quickSort(elements, 0, elements.length - 1);

        return elements;
    }

    private void quickSort(T[] elements, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = left;
        for (int i = pivot + 1; i <= right; i++) {
            if (elements[pivot].compareTo(elements[i]) > 0) {
                T less = elements[i];
                for (int j = i; j > pivot; j--) {
                    elements[j] = elements[j - 1];
                }

                elements[pivot] = less;
                pivot += 1;
            }
            LOGGER.info("left: {}, right: {}, pivot: {}, pivot element: {}, elements: {}", left, right, pivot, elements[pivot], elements);
        }

        //对左边的部分数组元素进行快速排序
        quickSort(elements, left, pivot - 1);

        //对右边的部分数组元素进行快速排序
        quickSort(elements, pivot + 1, right);
    }
}
